Digital halftoning converts image information comprising a large number of gray scaled pixel values to a reduced number of gray scaled pixel values in order that image information be rendered for display or hardcopy (printed) output. Image information, be it color or black and white, is commonly derived by scanning, initially at least, in a gray level format containing a large number of gray density levels, e.g.: 256 levels for black and white and more than 16 million (256.sup.3) levels for color, which is usually not reproducible on standard printing and display systems. The term "gray level" is used herein to described data for both black and white and color applications. For example, standard printing systems print in a limited number of levels, either a spot or a no spot in the binary case, or a limited number of levels associated with the spot, such as four in the quaternary case. Thus, image information encoded by a large number of gray level values must be converted to a fewer number of gray level values in order that the image information be rendered on typical display and printing systems.
One method of converting gray level pixel image data to binary level pixel image data is through the use of dithering or screening processes. In such arrangements, over a given area, each gray level pixel within the area is compared to one of a set of preselected thresholds, comprising a matrix of threshold values or a halftone cell. The effect of such an arrangement is that, for an area where the image is gray, some of the thresholds within the matrix will be exceeded, while others are not. In the binary case, the portions of the matrix, or cell elements, in which the thresholds are exceeded are printed as black, while the remaining elements are allowed to remain white. The effect of the distribution of black and white over the cell is integrated by the human eye as gray.
Dithering presents problems, however, in that the amount of gray within an original image is not maintained exactly over an area, because the finite number of elements inside each halftone cell only allows the reproduction of a finite number of gray levels. The error arising from the difference between the threshold value and the actual gray level value at any particular cell is simply thrown away. This results in loss of image information. Dithering creates significant image artifacts because it ignores this error completely, for example, bands or false contour artifacts, can be seen in smooth image areas. In this example, the image input gray level varies smoothly over an area while the halftoned image has to make a transition from one halftone dot (gray level) to another. This transition can clearly be seen as a band or pattern running through smooth image parts.
Other techniques exist that convert gray images to binary or a lesser level of gray while attempting to preserve gray density of the images. Error diffusion, for example, attempts to maintain gray density by making the conversion from gray pixels to binary or other level pixels on a pixel-by-pixel basis. The procedure examines each pixel value with respect to a threshold, and the difference between the gray level pixel value and the threshold is then forwarded to a selected group of neighboring pixels, in accordance with a weighting scheme. The corrected image pixels are then considered input to the processing. In this way, the error calculated includes all errors previously made.
Basic error diffusion is proposed by Floyd and Steinberg, in "An Adaptive Algorithm for Spatial Greyscale", Proceedings of the SID 17/2, 75-77 (1976) (hereinafter, "Floyd and Steinberg"). Modifications to the error diffusion algorithm taught by Floyd and Steinberg have been proposed, e.g.: a different weighting matrix, as taught, for example, in "A Survey of Techniques for the Display of Continuous Tone Pictures on Bi-level Displays" by Jarvis et al., Computer Graphics and Image Processing, Vol. 5., pp. 13-40 (1976), and in "MECCA--A Multiple-Error Correction Computation Algorithm for Bi-Level Image Hardcopy Reproduction" by Stucki, IBM Res. Rep. RZ1060 (1981). Other, examples of Floyed and Steinberg error diffusion technique having enhanced error calculation and weight allocation schemes include U.S. Pat. Nos. 5,208,871; 4,924,322; 4,339,774; 4,955,065; 5,045,952; 5,130,823; 5,014,333; 5,077,615; 4,969,052; 5,077,812; 4,876,610; and 4,733,230. Also of interest is U.S. patent application Ser. 07/755,380, entitled "Method For Quantization Gray Level Pixel Data With Application Of Under Compensated Error Diffusion" by R. Eschbach, which teaches a method for the application of under compensated error diffusion to a pixel quantizing method in the conversion of image data from a number of input levels that is relatively large with respect to a number of desired output levels.
An alternative error diffusion procedure is taught in "Images from computers" by M. R. Schroder (sometimes spelled Schroeder) in IEEE Spectrum, pp 66-78 (1969) (hereinafter Schroder). In this method the error is only calculated between the original input pixel and the output, neglecting all previously made errors. This method leads to a poorer gray level representation than Floyd and Steinberg but to higher image contrast. Modifications to the algorithm by Schroder are taught, for example, in "Design of Optimal Filters for Error-Feedback Quantization of Monochrome Pictures" by Jung Guk Kim and Gil Kim, Information Sciences 39, pp 285-298 (1986).
Since the Floyd and Steinberg error diffusion technique is not periodic in nature, it does not produce output images with repeating patterns in uniform image areas as does the dither or screening technique. Error diffusion, however, does introduce correlated patterns, sometimes called "worms", in uniform image areas particularly in shadow and highlight areas. Some schemes developed that try to minimize the worm effect are described by R. Ulichney in "Digital Halftoning", The MIT Press, Cambridge, Mass (1987), which include: using random weights or thresholds (e.g. U.S. Pat. No. 5,130,823); increasing the size of the selected group of neighboring pixels (or window size); and applying a "serpent scanning" technique to the input image so that adjacent lines of the input image are processed in opposite directions (e.g. U.S. Pat. No. 4,955,065). Since these improvements are coupled with new artifacts or with a rise in noise level, they only tend to alleviate the worm problem and not eliminate it. Disclosed in U.S. patent application Ser. No. 08/102,330 to Fan, entitled "Balanced Error Diffusion System", (also published as "Error Diffusion With A More Symmetric Error Distribution" in Human Vision, Visual Processing, and Digital Display V, Bernice E. Rogowitz, Jan P. Allebach, Editors, Proc. SPIE 2179, pp. 150-158 on Feb. 8-10, 1994) is a digital halftoning system that disperses quantization errors resulting from error diffusion to surrounding pixels using a forward pass and a backward pass.